#include <iostream>
#include <memory>
using namespace std;

class Trie {
private:
    bool isEnd = false;
    Trie* next[26];
public:
    Trie() {
        memset(next, 0, sizeof(next));
    }

    void insert(string word) {
        Trie* node = this;
        for (auto ch : word)
        {
            if (node->next[ch - 'a'] == nullptr)
                node->next[ch - 'a'] = new Trie;
            node = node->next[ch - 'a'];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this;
        for (auto ch : word)
        {
            if (node->next[ch - 'a'] == nullptr)
                return false;
            node = node->next[ch - 'a'];
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        Trie* node = this;
        for (auto ch : prefix)
        {
            if (node->next[ch - 'a'] == nullptr)
                return false;
            node = node->next[ch - 'a'];
        }
        return true;
    }
};


int main()
{

	return 0;
}